/** **********************************************************************************
 * @file    1.D.c
 * @mainpage
 * @date    2013-09-29 23:44
 * @author  Alexey Kulikov <alexeyqu@gmail.com>, group 376, DCAM MIPT
 * @version 1.00
 *
 * Binary words
 *
 * @par     The task.
 *          The program prints quantity of "good" binary words
 *          with determined length and amount of '1' symbols
 *
 * @note    NB: "Good" word is a word without "11" subsequences
 *
 * @warning Maximal length is 48
**************************************************************************************/

#include <stdlib.h>
#include <stdio.h>

#define MAX_LENGTH 49
#define DEBUG

#ifdef DEBUG
    #define DBG printf ("# "),
    #define ASSERT(cond)                                                              \
    if (!(cond))                                                                      \
    {                                                                                 \
        printf ("Critical failure in assertion '%s'! \nfile %s, line %d \n"           \
                "Now keep calm and EXTERMINATE! EXTERMINATE! EXTERMINATE!!!\n"        \
                , #cond, __FILE__, __LINE__);                                         \
        abort();                                                                      \
    }
#else
    #define DBG if (0)
    #define ASSERT(cond)
#endif

/** ********************************************************************************
 * Amount_Of_Words - fills the given table with quantities of "good" words with
 * i positions and j '1' symbols
 *
 * @param   GoodWordsQuant[][]  Amount-of-words table
 *          length              Length of concerned word
************************************************************************************/
void Amount_Of_Words (long long int goodWordsQuant[MAX_LENGTH][MAX_LENGTH], int length);

int main()
{
    DBG printf ("C language test'07. \n");
    DBG printf ("1.D problem. \n");
    DBG printf ("Calculate amount of \"good\" binary words (see docs)"
                "with determined maximum length \n");
    DBG printf ("Enter length to check: \n-> ");

    long long int goodWordsQuant[MAX_LENGTH][MAX_LENGTH] = {}; //!< Amount of good words with i positions and j '1'
    int length = 0; //!< Maximum considered word length
    int i = 0, j = 0; //!< Counters
    int res_input = 0; //!< Value that controls correct input

    res_input = scanf ("%d", &length);
    ASSERT (res_input); ASSERT (length >= 0); ASSERT (length < MAX_LENGTH);

    Amount_Of_Words (goodWordsQuant, length);

    DBG printf ("Result: \n");

    //! Printing result
    for (i = 0; i <= length; i++)
    {
        for (j = 0; j <= i; j++)
        {
            if (goodWordsQuant[i][j] == 0) break;
            else printf ("%lld ", goodWordsQuant[i][j]);
        }
        printf ("\n");
    }

    return 0;
}

void Amount_Of_Words (long long int goodWordsQuant[MAX_LENGTH][MAX_LENGTH], int length)
{
    int i = 0, j = 0; //!< Counters

    //! Determining start values
    for (i = 0; i <= length; i++)
    {
        goodWordsQuant[i][0] = 1;
        goodWordsQuant[i][1] = i;
    }

    //! Recurrent computing
    for (i = 0; i <= length; i++)
    {
        for (j = 2; j <= i; j++)
        {
            ASSERT (i - 2 >= 0); ASSERT (j - 1 >= 0);
            goodWordsQuant[i][j] = goodWordsQuant[i - 1][j] + goodWordsQuant[i - 2][j - 1];
        }
    }
}
